The CUR matrix decomposition is an important extension of Nystr\"{o}mapproximation to a general matrix. It approximates any data matrix in terms ofa small number of its columns and rows. In this paper we propose a novelrandomized CUR algorithm with an expected relative-error bound. The proposedalgorithm has the advantages over the existing relative-error CUR algorithmsthat it possesses tighter theoretical bound and lower time complexity, and thatit can avoid maintaining the whole data matrix in main memory. Finally,experiments on several real-world datasets demonstrate significant improvementover the existing relative-error algorithms.
展开▼
